/*
 * Copyright (c) 2019 Wormpex.com. All Rights Reserved.
 */

package com.sk.leetcode.arithmetic;

/**
 * @author ke.su date: 2019-06-20 Time: 下午7:49
 * 接雨水，和84 算是同一类型
 * <p>
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水。
 * <p>
 * 示例:
 * <p>
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 */

public class Test42 {

    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int sum = trap(height);
        System.out.println(sum);
    }


    public static int trap(int[] height) {
        int length = height.length;
        int sum = 0;

        int k = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if(height[i] <= height[j]) {
                    k = j;
                    i = j;
                    j = length;
                }
            }

            int min = 0, w = 0;
            if(i == k - 1) {
                continue;
            }
            for (int l = i + 1; l < k; l++) {
                min += height[l];
                w++;
            }

            sum += (w * (height[i] >= height[k] ? height[k] : height[i]));

        }
        return sum;
    }
}
